%{
    open Ast
%}

/* 词法单元token定义 */
%token <int> NUMBER
%token <string> ID
%token PLUS MINUS TIMES DIV MOD
%token LPAREN RPAREN LBRACE RBRACE
%token SEMICOLON COMMA
%token EQ NEQ LT GT LEQ GEQ AND OR NOT ASSIGN
%token INT_TYPE VOID
%token IF ELSE WHILE BREAK CONTINUE RETURN
%token EOF

/* 在 token 声明中使用 Tokens 模块 
%token <int> Tokens.NUMBER
%token <string> Tokens.ID
%token Tokens.PLUS Tokens.MINUS Tokens.TIMES Tokens.DIV Tokens.MOD
%token Tokens.LPAREN Tokens.RPAREN Tokens.LBRACE Tokens.RBRACE
%token Tokens.SEMICOLON Tokens.COMMA Tokens.ASSIGN
%token Tokens.EQ Tokens.NEQ Tokens.LT Tokens.GT Tokens.LEQ Tokens.GEQ Tokens.AND Tokens.OR Tokens.NOT
%token Tokens.INT_TYPE Tokens.VOID
%token Tokens.IF Tokens.ELSE Tokens.WHILE Tokens.BREAK Tokens.CONTINUE Tokens.RETURN
%token Tokens.EOF*/

/* 规定运算符优先级和结合性 */
%nonassoc BELOW_ELSE
%nonassoc ELSE
%left OR
%left AND
%left EQ NEQ
%left LT GT LEQ GEQ
%left PLUS MINUS
%left TIMES DIV MOD
%nonassoc unary

/* 语法分析入口 
%start program
%type <Ast.program> program
%%*/

%start <Ast.program> program
%type <Ast.func_def list> func_def_list
%type <Ast.func_def> func_def
%type <Ast.ty> ret_type
%type <Ast.param list> param_list
%type <Ast.param> param
%type <Ast.stmt> block
%type <Ast.stmt list> stmt_list
%type <Ast.stmt> stmt
%type <Ast.expr> expr
%type <Ast.expr> l_or_expr
%type <Ast.expr> l_and_expr
%type <Ast.expr> rel_expr
%type <Ast.expr> add_expr
%type <Ast.expr> mul_expr
%type <Ast.expr> unary_expr
%type <Ast.expr> primary_expr
%type <Ast.expr list> arg_list
%%

program:
    | func_def_list EOF { $1 }
;

func_def_list:
    | func_def { [$1] }
    | func_def func_def_list { $1 :: $2 }
;

func_def:
    | ret_type ID LPAREN param_list RPAREN block 
        { { return_ty = $1; name = $2; params = $4; body = $6 } }
;

ret_type:
    | INT_TYPE { Int }
    | VOID { Void }
;

param_list:
    | /* empty */ { [] }
    | param { [$1] }
    | param COMMA param_list { $1 :: $3 }
;

param:
    | INT_TYPE ID { Param(Int, $2) }
;

block:
    | LBRACE stmt_list RBRACE { Block(List.rev $2) }
;

/* 语句序列 */
stmt_list:
    | /* empty */ { [] }
    | stmt_list stmt { $2 :: $1 }
;

stmt:
    | block { $1 }
    | SEMICOLON { Empty }
    | expr SEMICOLON { ExprStmt($1) }
    | ID ASSIGN expr SEMICOLON { AssignStmt($1, $3) }
    | INT_TYPE ID ASSIGN expr SEMICOLON { VarDecl($2, Some $4) }
    | INT_TYPE ID SEMICOLON { VarDecl($2, None) }
    | IF LPAREN expr RPAREN stmt %prec BELOW_ELSE { If($3, $5, None) }
    | IF LPAREN expr RPAREN stmt ELSE stmt { If($3, $5, Some $7) }
    | WHILE LPAREN expr RPAREN stmt { While($3, $5) }
    | BREAK SEMICOLON { Break }
    | CONTINUE SEMICOLON { Continue }
    | RETURN SEMICOLON { Return None }
    | RETURN expr SEMICOLON { Return (Some $2) }
;

expr:
    | l_or_expr { $1 }
;

l_or_expr:
    | l_and_expr { $1 }
    | l_or_expr OR l_and_expr { Binop(Or, $1, $3) }
;

l_and_expr:
    | rel_expr { $1 }
    | l_and_expr AND rel_expr { Binop(And, $1, $3) }
;

rel_expr:
    | add_expr { $1 }
    | rel_expr LT add_expr { Binop(Lt, $1, $3) }
    | rel_expr GT add_expr { Binop(Gt, $1, $3) }
    | rel_expr LEQ add_expr { Binop(Leq, $1, $3) }
    | rel_expr GEQ add_expr { Binop(Geq, $1, $3) }
    | rel_expr EQ add_expr { Binop(Eq, $1, $3) }
    | rel_expr NEQ add_expr { Binop(Neq, $1, $3) }
;

add_expr:
    | mul_expr { $1 }
    | add_expr PLUS mul_expr { Binop(Add, $1, $3) }
    | add_expr MINUS mul_expr { Binop(Sub, $1, $3) }
;

mul_expr:
    | unary_expr { $1 }
    | mul_expr TIMES unary_expr { Binop(Mul, $1, $3) }
    | mul_expr DIV unary_expr { Binop(Div, $1, $3) }
    | mul_expr MOD unary_expr { Binop(Mod, $1, $3) }
;

unary_expr:
    | primary_expr { $1 }
    | PLUS unary_expr %prec unary { Unop(Plus, $2) }
    | MINUS unary_expr %prec unary { Unop(Minus, $2) }
    | NOT unary_expr %prec unary { Unop(Not, $2) }
;

primary_expr:
    | NUMBER { Number $1 }
    | ID { Var $1 }
    | LPAREN expr RPAREN { $2 }
    | ID LPAREN arg_list RPAREN { Call($1, $3) }
    | ID ASSIGN expr { Assign($1, $3) }  /* 允许赋值作为表达式 */
;

/* 函数参数列表 */
arg_list:
    | /* empty */ { [] }
    | expr { [$1] }
    | expr COMMA arg_list { $1 :: $3 }
;